/*
 * @lc app=leetcode.cn id=1011 lang=cpp
 *
 * [1011] 在 D 天内送达包裹的能力
 */

// @lc code=start
class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int low = *max_element(weights.begin(), weights.end());
        int high = accumulate(weights.begin(), weights.end(), 0);
        while (low < high) {
            int cap = low + (high - low) / 2;
            int day = need(weights, cap);
            if (day > days) {
                low = cap + 1;
            } else {
                high = cap;
            }
        }
        return low;
    }

    int need(vector<int>& weights, int cap) {
        int day = 1;
        int rest = cap;
        for (int weight : weights) {
            if (rest - weight >= 0) {
                rest -= weight;
            } else {
                day++;
                rest = cap - weight;
            }
        }
        return day;
    }
};
// @lc code=end

